package day01;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/1/1 11:23
 */

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：
 *
 * left <= nums1 < nums2 <= right  。
 * nums1 和 nums2 都是 质数 。
 * nums2 - nums1 是满足上述条件的质数对中的 最小值 。
 * 请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。
 *
 * 如果一个整数大于 1 ，且只能被 1 和它自己整除，那么它是一个质数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：left = 10, right = 19
 * 输出：[11,13]
 * 解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。
 * 质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。
 * 由于 11 比 17 小，我们返回第一个质数对。
 * 示例 2：
 *
 * 输入：left = 4, right = 6
 * 输出：[-1,-1]
 * 解释：给定范围内只有一个质数，所以题目条件无法被满足。
 */
public class Solution5 {
    public int[] closestPrimes(int left, int right) {
        List<Integer> list = new ArrayList<>();
        for(int i = left;i<=right;i++){
            if(is_prime(i)){
                list.add(i);
            }
        }
        if(list.size()<=1){
            return new int[]{-1,-1};
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int a = o1[1] - o1[0];
                int b = o2[1] - o2[0];
                return a-b;
            }
        });
        for (int i = 1; i < list.size(); i++) {
            pq.add(new int[]{list.get(i-1),list.get(i)});
        }
        return pq.peek();
    }
    public boolean is_prime(int x)
    {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= x / i; i ++ ) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}
